package de.ifgi;

import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.nio.charset.Charset;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

import android.content.Context;
import android.util.Log;

import com.csvreader.CsvReader;

/**
 * Reference:
 * <ul><li>http://www.vogella.de/articles/JavaAlgorithmsDijkstra/article.html
 * <li>http://renaud.waldura.com/doc/java/dijkstra/
 * </ul>
 * @author freska
 *
 */
public class Routing {

	private static final String tag = "OIL";
	private Set<Vertex> settledVertices;
	private Set<Vertex> unsettledVertices;
	private Map<Vertex, Vertex> hmPredecessors;
	private Map<Vertex, Double> hmDistance;
	private List<Vertex> vertices;
	private List<Edge> edges;
	
	public Routing(Context ctx) {
		super();
		init(ctx);
		considerEvents();
	}
	
	public void considerEvents() {
		EventsList eventsList = EventsList.getEventsList();
//		List<Event> eventsList = new ArrayList<Event>();
//		Event e1 = new Event("1", "1", new Point(404474.320, 5755414.861));
//		eventsList.add(e1);
		
		if (eventsList.size() > 0) {
			double minDist = Double.MAX_VALUE;
			Vertex v2 = null;

			for (Event e : eventsList) {
				// get a vertex closest to the event position
				Vertex v1 = toVertex(e.getEstPosition());
				Log.d(tag, "closest vertex="+v1.getId());

				// get the neighbours
				for (Edge edge : edges) {
					if (edge.getFrom().equals(v1)) {
						// for each neighbour, search for one having closest distance to the event
						// in other words, we're searching for edges on which the event occured
						double d = e.getEstPosition().distance(edge.getTo().getPos());
						if (d < minDist) {
							minDist = d;
							v2 = edge.getTo(); // the closest neighbour
						}
					}
				}

				Log.d(tag, "neighbour="+v2.getId());

				// look for the edge and change the weights to maximum
				for (Edge edge : edges) {
					if (edge.getFrom().equals(v1) && edge.getTo().equals(v2) || edge.getFrom().equals(v2) && edge.getTo().equals(v1)) {
						edge.setDist(Double.MAX_VALUE);
						Log.d(tag, "unavailable from "+v1.getId()+" to "+v2.getId());
					}
				}
			}
		}
		
	}
	
	public List<Point> generateRoute(Point userPos, Point exitPos) {
        long startTime = System.currentTimeMillis();
        
//		for (Edge e : edges) {
//			Log.d(tag, "from "+e.getFrom().getId()+" to "+e.getTo().getId()+" dist="+e.getDist());
//		}
		Vertex src = toVertex(userPos);
		Vertex dst = vertices.get(0);
		
		settledVertices = new HashSet<Vertex>(); // S
		
		unsettledVertices = new HashSet<Vertex>(); // Q
		unsettledVertices.add(src);
		
		hmDistance = new HashMap<Vertex, Double>();
		hmDistance.put(src, 0.0);
		
		hmPredecessors = new HashMap<Vertex, Vertex>();
		
		while (!unsettledVertices.isEmpty()) {
			Vertex min = extractMin(unsettledVertices);			
			settledVertices.add(min);
			if (min == dst)
				break;
			relaxNeighbours(min);
		}
		
		List<Vertex> path = getPath(dst);
		
		List<Point> route = new ArrayList<Point>();
		for (Vertex v : path) {
			Log.d(tag, "path="+v.getId());
			route.add(v.getPos());
		}
		
		long stopTime = System.currentTimeMillis();
        Log.d(tag, "\nTime taken=" + (stopTime-startTime) + " ms");
		return route;
	}
	
	private Vertex toVertex(Point pos) {
		double minDist = Double.MAX_VALUE;
		Vertex vPos = null;
		for (Vertex v : vertices) {
			double d = v.getPos().distance(pos);
			Log.d(tag, "v="+v.getId()+" dist="+d);
			if (d < minDist) {
				minDist = d;
				vPos = v;
			}
		}
		Log.d(tag, "minDist="+minDist);
		return vPos;
	}

	public List<Vertex> getPath(Vertex dst) {
		List<Vertex> path = new LinkedList<Vertex>();
		// check if a path exists
		if (hmPredecessors.get(dst) == null) {
			return null;
		}
		path.add(dst);
		while (hmPredecessors.get(dst) != null) {
			dst = hmPredecessors.get(dst);
			path.add(dst);
		}
		// put it into the correct order
		Collections.reverse(path);
		return path;
	}
	
	private List<Vertex> getNeighbours(Vertex v) {
		List<Vertex> neighbours = new ArrayList<Vertex>();
		for (Edge e : edges) {
			if (e.getFrom().equals(v) && !isSettled(e.getTo())) {
				neighbours.add(e.getTo());
			}
		}
		return neighbours;
	}
	
	private void relaxNeighbours(Vertex min) {
		List<Vertex> neighbours = getNeighbours(min);			
		
		for (Vertex v : neighbours) {
//			Log.d(tag, "neighbours="+v.getId());
			if (getShortestDistance(min) + getDistance(min, v) < getShortestDistance(v)) {
				hmDistance.put(v, getShortestDistance(min) + getDistance(min, v));
				hmPredecessors.put(v, min);
				unsettledVertices.add(v);
			}
		}
	}

	private Vertex extractMin(Set<Vertex> unsettledVertices) {
		Vertex min = null;
		for (Vertex v : unsettledVertices) {
			if (min == null) {
				min = v;
			} else {
				if (getShortestDistance(v) < getShortestDistance(min)) {
					min = v;
				}
			}
		}
		unsettledVertices.remove(min);
		return min;
	}
	
	private boolean isSettled(Vertex v) {
		return settledVertices.contains(v);
	}
	
	private double getDistance(Vertex src, Vertex dst) {
		double d = Double.MAX_VALUE;
		for (Edge edge : edges) {
			if (edge.getFrom().equals(src) && edge.getTo().equals(dst)) {
				d = edge.getDist();
			}
		}
		return d;
	}
	
	private double getShortestDistance(Vertex dst) {
		if (hmDistance.get(dst) == null) {
			return Double.MAX_VALUE;
		} else {
			return hmDistance.get(dst);
		}
	}
	
	/**
	 * Init graph - list of vertices and edges
	 */
	private void init(Context ctx) {
		// parse CSV to read vertices (nodes)
		InputStream is;
		CsvReader reader;
		
		is = ctx.getResources().openRawResource(R.raw.vertices);		
		vertices = new ArrayList<Vertex>();
		
		try {
			reader = new CsvReader(is, Charset.defaultCharset());
			reader.readHeaders();
			while (reader.readRecord()) {
				String id = reader.get("id");
				String pos[] = reader.get("pos").split(" ");
				String name = reader.get("name");
				Vertex v = new Vertex(id, new Point(Double.parseDouble(pos[0]), Double.parseDouble(pos[1])), name);
				vertices.add(v);
			}
			reader.close();
		} catch (FileNotFoundException e) {
			Log.d(tag, "File not found");
		} catch (IOException e) {
			Log.d(tag, "Exception in reading");
		}
		
		// parse CSV to read edges
		is = ctx.getResources().openRawResource(R.raw.edges);
		edges = new ArrayList<Edge>();
		
		try {
			reader = new CsvReader(is, Charset.defaultCharset());
			reader.readHeaders();
			while (reader.readRecord()) {
				String from = reader.get("from");
				String to = reader.get("to");
				String dist = reader.get("dist");
				Edge e = new Edge(vertices.get(Integer.parseInt(from)-1), vertices.get(Integer.parseInt(to)-1), 
						Double.parseDouble(dist));
				edges.add(e);
			}
			reader.close();
		} catch (FileNotFoundException e) {
			Log.d(tag, "File not found");
		} catch (IOException e) {
			Log.d(tag, "Exception in reading");
		}
		
	}
	
}
